//在由 1 x 1 方格组成的 N x N 网格 grid 中，每个 1 x 1 方块由 /、\ 或空格构成。这些字符会将方块划分为一些共边的区域。 
//
// （请注意，反斜杠字符是转义的，因此 \ 用 "\\" 表示。）。 
//
// 返回区域的数目。 
//
// 
//
// 
// 
//
// 示例 1： 
//
// 输入：
//[
//  " /",
//  "/ "
//]
//输出：2
//解释：2x2 网格如下：
// 
//
// 示例 2： 
//
// 输入：
//[
//  " /",
//  "  "
//]
//输出：1
//解释：2x2 网格如下：
// 
//
// 示例 3： 
//
// 输入：
//[
//  "\\/",
//  "/\\"
//]
//输出：4
//解释：（回想一下，因为 \ 字符是转义的，所以 "\\/" 表示 \/，而 "/\\" 表示 /\。）
//2x2 网格如下：
// 
//
// 示例 4： 
//
// 输入：
//[
//  "/\\",
//  "\\/"
//]
//输出：5
//解释：（回想一下，因为 \ 字符是转义的，所以 "/\\" 表示 /\，而 "\\/" 表示 \/。）
//2x2 网格如下：
// 
//
// 示例 5： 
//
// 输入：
//[
//  "//",
//  "/ "
//]
//输出：3
//解释：2x2 网格如下：
//
// 
//
// 
//
// 提示： 
//
// 
// 1 <= grid.length == grid[0].length <= 30 
// grid[i][j] 是 '/'、'\'、或 ' '。 
// 
// Related Topics 深度优先搜索 并查集 图 
// 👍 165 👎 0
#include <iostream>
#include <numeric>
#include <vector>

using namespace std;

class UnionFind {
public:
    vector<int> parent;
    vector<int> size;
    int n;
    int setCount;
public:
    UnionFind(int _n) : n (_n),setCount(_n),parent(_n),size(_n,1){
        //iota(parent.begin(),parent.end(),0);
        for (int i = 0; i < _n; ++i) {
            parent[i] = i;
        }
    }

    int findSet(int x){
        return parent[x] == x ? x : findSet(parent[x]);
    }

    bool uniteSet(int x ,int y){
        int x0 = findSet(x);
        int y0 = findSet(y);
        if (x0 == y0){
            return false;
        }
        if (size[x0] < size[y0]){
            swap(x0,y0);
        }
        parent[y0] = x0;
        size[x0] += size[y0];
        --setCount;
        return true;
    }

    bool connected(int x,int y){
        int x0 = findSet(x);
        int y0 = findSet(y);

        return x0 == y0;
    }

};

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public:
    int regionsBySlashes(vector<string>& grid) {
        int len = grid.size();
        UnionFind uf(len*len*4);
        for (int i = 0; i < len; ++i) {
            for (int j = 0; j < len; ++j) {
                int index = i * len + j;
                //考虑相邻区域的三角形连接
                if (i < len-1){
                    int bottom = index + len;
                    uf.uniteSet(index * 4 + 2,bottom * 4);
                }
                if (j < len - 1){
                    int rightEdge = index + 1;
                    uf.uniteSet(index * 4 + 1,rightEdge * 4 + 3);
                }

                //考虑内部四个方块合并的情况
                if (grid[i][j] == '/'){
                    uf.uniteSet(index * 4 , index * 4 +3);
                    uf.uniteSet(index * 4 + 1, index * 4 + 2);
                } else if (grid[i][j] == '\\'){
                    uf.uniteSet(index * 4 , index * 4 + 1);
                    uf.uniteSet(index * 4 +2 , index * 4 + 3);
                } else {
                    uf.uniteSet(index * 4,index * 4 +1);
                    uf.uniteSet(index * 4 + 1, index * 4 +2);
                    uf.uniteSet(index * 4 + 2, index * 4 + 3);
                }
            }
        }

        return uf.setCount;
    }
};
//leetcode submit region end(Prohibit modification and deletion)
